/*
 * ArbreGenealogique.cpp
 *
 *  Created on: 2013-11-29
 *      Author: Jean-Simon,Simon
 */
#include "ArbreGenealogique.h"
#include "Personne.h"

namespace tp3
{
/*
 * \fn	ArbreGenealogique::ArbreGenealogique(Personne &p_personne)
 * \brief	Constructeur
 * \post 	l'arbre contient un noeud référençant une personne (l'ancètre)
 * \post	le nom de l'arbre est celui de la personne passée en paramètre
 */
ArbreGenealogique::ArbreGenealogique(Personne &p_personne)
{
	m_racine = new Noeud(p_personne);
}

/*
 * \fn	ArbreGenealogique::~ArbreGenealogique()
 * \brief Destructeur
 */
ArbreGenealogique::~ArbreGenealogique()
{
	m_racine = 0;
}

/**
 * \fn		void ArbreGenealogique::ajouterEnfant(Personne& p_parent, Personne& p_enfant)
 * \brief	Ajouter une personne dans un arbre genealogique soit ajouter un enfant au parent.
 *
 * \param[in]	p_enfant	la référence d'une personne
 * \param[in]	p_parent	la référence d'une personne
 *
 * \exception	logic_error	logic_error	si arbre vide ou parent absent
 *
 */
void ArbreGenealogique::ajouterEnfant(Personne& p_parent, Personne& p_enfant)
{
	if(m_racine == 0)
		throw std::logic_error("L'arbre est vide");

	if(!appartient(p_parent))
		throw std::logic_error("Le parent n'existe pas");

	Noeud* parent;
	trouvePersonne(p_parent, parent);

	for(Noeud* fils = parent; fils != 0; fils = fils->m_gauche)
	{
		if(fils->m_gauche == 0)
			fils->m_gauche = new Noeud(p_enfant);
	}
}

/**
 * \fn		std::vector<Personne*> ArbreGenealogique::enfantsDe(const Personne& p_parent) const
 * \brief	trouver tous les enfants du parent
 *
 * \param[in]	le parent des enfants
 * \return	un vecteur contenant tous les enfants
 */
std::vector<Personne*> ArbreGenealogique::enfantsDe(
		const Personne& p_parent) const
{
	std::vector<Personne*> v;
	Noeud* i;
	for(_trouvePersonne(m_racine, p_parent, i); i != 0; i = i->m_droite)
	{
		v.push_back(i->m_personne);
	}
	return v;
}

/**
 *	\fn		bool ArbreGenealogique::appartient(const Personne& p_personne) const
 *	\brief	permet de savoir si une personne appartient à l'arbre
 *
 * 	\param[in]	p_personne	la personne recherchée.
 * 	\return		vrai si la personne est dans l'arbre, faux sinon.
 */
bool ArbreGenealogique::appartient(const Personne& p_personne) const
{
	Noeud* trouve = 0;
	_trouvePersonne(m_racine, p_personne, trouve);
	return trouve != 0;
}

/**
 * \fn
 * \brief	trouve l'adresse du noeud où se trouve la personne par parcours récursif pré-ordre de _trouvePersonne
 *
 * \param[in]	p_personne	la personne recherchée
 * \param[in]	p_trouve	le noeud trouvé
 *
 * \post	Postcondition le noeud est trouvé, si non ==0
 */
void ArbreGenealogique::trouvePersonne(const Personne& p_personne,
		Noeud*& p_trouve) const
{
	_trouvePersonne(m_racine, p_personne, p_trouve);
}

void ArbreGenealogique::_trouvePersonne(Noeud* p_racine,
		const Personne& p_personne, Noeud*& p_trouve) const
{
	Noeud* visit = p_racine;
	std::list<Noeud*> v;
	while(!v.empty() || visit != 0)
	{
		if(true/*visit->m_personne == p_personne*/)
		{
			p_trouve = visit;
			break;
		}

		if(visit != 0)
		{
			if(visit->m_droite != 0)
			{
				v.push_front(visit->m_droite);
			}
			visit = visit->m_gauche;
		}
		else
			visit = v.back();
			v.pop_back();
	}
}

void ArbreGenealogique::_postOrdre(Noeud* p_Ncourant,
		std::vector<Personne*>& p_vPersonnes) const
{
	if (p_Ncourant != 0)
	    {
	        p_vPersonnes.push_back(p_Ncourant->m_personne);
	        _postOrdre(p_Ncourant->m_droite, p_vPersonnes);
	        _postOrdre(p_Ncourant->m_gauche, p_vPersonnes);
	    }
}
}

